#! /usr/bin/env python3
# coding= utf-8

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution(object):
    def _reverseKGroup(self, head, k):
        if None is head:
            return
        if k == 1:
            return head
        start = head
        res, steps = self.mov_forward(start, k - 1)
        if(steps != k - 1):
            return head
        last_end = None
        next_start = None
        while start is not None:
            end, n = self.mov_forward(start, k - 1)
            if (n != k - 1):
                self._connect(last_end, start)
            next_start = end.next
            self._reverse(start, end)
            if last_end is not None:
                self._connect(last_end, end)
            last_end = start
            start = next_start
        return res
    @staticmethod
    def happy_reverse(begin, end):
        curr = begin.next
        prev = begin
        begin.next = None
        while curr is not end:
            next = curr.next
            curr.next = prev
            prev = curr
            curr = next
        return prev
    def reverseKGroup(self, head, k):
        if None is head or k < 2:
            return head

        i = 0
        new_head = ListNode(None)
        new_tail = new_head
        cur = head
        begin = head
        joint = new_head
        while True:
            new_tail.next = cur
            if i % k == 0 and i != 0:
                end = cur
                _joint = self.happy_reverse(begin, end)
                joint.next = _joint
                begin.next = end
                joint = begin
                begin = end
            else:
                new_tail.next = cur
                new_tail = cur

            cur = cur.next
            if cur is None:
                break
            i += 1
        return new_head.next



    @staticmethod
    def mov_forward(node, n):
        for i in range(n):
            if node.next is not None:
                node = node.next
            else:
                return node, i
        return node, i + 1

    def _reverse(self, head, tail):
        res = ListNode(None)
        while True:
            tmp = head
            head = head.next
            tmp.next = res.next
            res.next = tmp
            if tmp is tail:
                break
        return res.next

    @staticmethod
    def _connect(prev, next):
        prev.next = next

head = ListNode(None)
test = [1, 2, 3, 4]
prev = head
for i in test:
    node = ListNode(i)
    prev.next = node
    prev = node

def print_list(head):
    n = head
    while n is not None:
        print(n.val, end=" ")
        n = n.next



#h = reverse(head.next, None)
s = Solution()
h = s.reverseKGroup(head.next, 3)
print_list(h)

